#define DEBUG
#include <cstdio>
#define MAXN 1000000

using namespace std;

void solve(int o, int n, int *a, int *b, int ans[][2]) {
  static bool book[MAXN+1];
  static int now[MAXN+1][2];
  if (o<=n) {
    if ((!book[o]) && (!book[a[o]])) {
      book[o] = book[a[o]] = true;
      now[++now[0][0]][0] = o;
      now[now[0][0]][1] = a[o];
      now[0][1] += b[o]!=b[a[o]];
      solve(o+1, n, a, b, ans);
      now[0][1] -= b[o]!=b[a[o]];
      now[0][0]--;
      book[o] = book[a[o]] = false;
    }
    solve(o+1, n, a, b, ans);
  } else {
    bool flag=false;
    if (ans[0][0]<now[0][0]) {
      flag = true;
    } else if (ans[0][0]==now[0][0] && ans[0][1]<now[0][1]) {
      flag = true;
    }
    if (flag) {
      for (int i=0; i<=now[0][0]; i++) {
	ans[i][0] = now[i][0], ans[i][1] = now[i][1];
      }
    }
  }
}

int main() {
#ifdef DEBUG
  freopen("2.in", "r", stdin);
  freopen("2.out", "w", stdout);
#endif

  int t;
  scanf("%d", &t);
  for (int ti=1; ti<=t; ti++) {
    static int a[MAXN+1], b[MAXN+1], ans[MAXN/2+1][2];
    int n;
    scanf("%d", &n);
    for (int i=1; i<=n; i++) {
      scanf("%d %d", a+i, b+i);
    }
    ans[0][0]=ans[0][1]=0;
    solve(1, n, a, b, ans);
    for (int i=0; i<=ans[0][0]; i++) {
      printf("%d %d\n", ans[i][0], ans[i][1]);
    }
  }

  fclose(stdin);
  fclose(stdout);
  return 0;
}
